package a04_字符串;

/**
 * <p>
 * a07_重复的子字符串复习4
 * </p>
 *
 * @author flyduck
 * @since 2025/1/15
 */
public class a07_重复的子字符串复习4 {
    public static void main(String[] args) {
//        int[] nextArray = getNextArray("aabaab".toCharArray());
//        System.out.println();
        boolean abac = repeatedSubstringPattern("abac");
    }
    public static boolean repeatedSubstringPattern(String s) {
        char[] chars = s.toCharArray();
        int[] nextArray = getNextArray(chars);
        if (nextArray[nextArray.length - 1] == 0) {
            return false;
        }
        return chars.length % (chars.length - nextArray[nextArray.length - 1]) == 0;
    }

    private static int[] getNextArray(char[] chars){
        if (chars.length == 1) {
            return new int[]{-1};
        }
        int[] nextArray = new int[chars.length + 1];
        nextArray[0] = -1;
        nextArray[1] = 0;
        int currentIdx = 2;
        int compareIdx = nextArray[currentIdx - 1];
        while (currentIdx < nextArray.length) {
            if(chars[currentIdx - 1] == chars[compareIdx]){
                nextArray[currentIdx] = compareIdx + 1;
                currentIdx++;
                compareIdx = nextArray[currentIdx - 1];
            }else {
                if(compareIdx == 0){
                    nextArray[currentIdx] = 0;
                    currentIdx++;
                    compareIdx = nextArray[currentIdx - 1];
                }else {
                    compareIdx = nextArray[compareIdx];
                }
            }
        }
        return nextArray;
    }
}
